引言：HashMap
相信ArrayList和HashMap是大家日常用的最多的两个容器了。HashMap利用对key做哈希值，实现对任何元素直接下标访问。碰撞不严重的情况下O(1)的访问效率成了它最大的招牌。前几天想了解一下JDK源码中HashMap哈希值的具体算法，没想到相关的文章非常少，还基本是东一榔头西一棒。所以在自己花了很多时间弄清楚其中的原理之后，在此做个记录。
HashMap的内部数据结构
我们的故事从这张图开始，
HashMap内部是由一个Array和一系列的LinkedList组成的。我们都知道，HashMap用来储存这种电话本一类的数据是最好了。如上图所示，插入因元素put(K key, V value)方法的步骤如下：
- 创建一个Array数组，假设长度为16
- 以人名Jack Williams为key值，计算哈希值
- 得到的哈希值比如54896对数组的长度16-1取模运算。
- 以模运算的余数10为下标，直接储存到array[10]里。
- 如果发生碰撞，比如Andrew Wilson的哈希值为60810，余数还是10，这是就要以LinkedList的形式链接到Jack Williams的后面。
- 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树（Java 8的新特性）
- 如果节点已经存在就替换old value(保证key的唯一性)
- 如果bucket满了(超过load factorcurrent capacity)，就要resize。resize的时候，数组长度2。
根据以上的步骤，一般情况下，HashMap插入一个新元素，put(K key, V value)动作是常数复杂度O(1)。最坏情况碰撞严重，LinkedList是O(n)。Java 8加入红黑树后，最坏情况也顶多O(logn)。还是很给力的。
下面关门放代码：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
//hash(key)哈希值算法
int hash = hash(key);
int i = indexFor(hash, table.length);
//如果bucket槽非空，遍历相同bucket槽中LinkedList的所有节点。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//检验唯一性。如要修改需要重写hashCode()和equals()两个方法
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//检查线程安全
modCount++;
//插入新元素
addEntry(hash, key, value, i);
return null;
}
这里哈希算法是放到另外一个独立方法hash()里的。我们稍后重点介绍。
这里可以看到当元素发生碰撞的时候，HashMap会遍整个LinkedList，直到找到Key值相同的元素。这个源码是Java 7的，所以还没有检查LinkedList长度，转换成红黑树的代码。
这里，HashMap对Key值唯一性的检验标准，需要通过哈希值hashCode()，和equals()两个函数的验证。对这个问题，后面会再提到。最后插入新元素，调用addEntry()函数来完成：
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩展数组
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//实际插入元素的函数
createEntry(hash, key, value, bucketIndex);
}
可以看到addEntry()函数还不是最终完成插入函数的地方，还要调用createEntry()函数。 这里addEntry()主要负责检查负载，必要时扩展数组。另外，这个函数还调用indexFor()函数完成了哈希值到数组下标的转换。下标计算是用的“与”操作。只有两位都是1，才返回1，其余都返回零。其实就相当于一个掩码的作用。
static int indexFor(int h, int length) {
return h & (length-1);
}
比如HashMap的初始大小默认是16。16-1=15。 二进制就是00001111。“h & 15”的数学意义就是：只保留h二进制的后四位的值，其他都归零。相当于一个低位掩码。
0000 1111
& 1010 0101
-----------------
0000 0101 //保留末尾四位，高位归零
真正插入新节点的函数createEntry()代码如下：
void createEntry(int hash, K key, V value, int bucketIndex) {
//复制引用
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
到这里，HashMap的基本结构就清楚了。下面来细究一下HashMap使用的是什么哈希算法。
源代码中实际功能的代码块：hash( )函数
不废话，直接上hash()函数的源码：
final int hash(Object k) {
int h = 0;
//这个特殊选项先不去管它
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
//第一件事：调用Key自带的hashCode()函数获得初始哈希值
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
//初始哈希值做进一步优化（注：^为“异或”操作）
//异或：每一位上的值相同返回0，不同返回1。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
代码很简单，主要做了两件事：
- 调用key类型自带的hashCode()函数，计算原始哈希值。
- 拿到原始哈希值之后，做进一步优化：4次位移异或操作。（注：^为“异或”操作。异或：每一位上的值相同返回0，不同返回1。）
下面对这两步一一分析。
哈希值计算函数hashCode( )
查Java手册发现，hashCode()函数可以追溯到对象接口中定义的Object.hashCode()方法。我们看看OverStackFlow对hash函数相关问题最高票答案对此的解释：
hashCode()是每个对象自带的方法。但几乎每个类都会重写这个方法。所以hashCode()的哈希值计算方法每种数据类型都是不同的。
也就是说每一种类型的哈希算法都不同，都是自定义的。乍一看很神秘，其实非常简单。Java官方文档只规定程序员自定义的hashCode()方法需要满足下面三个条件，
- 第一，同一个object每次必须返回相同哈希值。无论使用它哪个引用。
- 第二，两个equals()判断相等的Object必须返回相同哈希值。
- 第三，两个equals()函数判断不相等的Object不需要一定返回不相等的hash值。
第三条最逗逼，简直是宣布哈希函数你们想怎么写怎么写吗。其实大部分常用数据类型的哈希值算法是非常萌的。比如说最常用的Integer就是返回它自己。
public int hashCode() {
return value;
}
Character返回的就是字符本身对应的ASCII码值。
int More ...hashCode() {
return (int)value;
}
String稍微复杂一点。但因为在《Effective Java》里被Joshua Bloch提到了，大家都知道了其中的魔法数字31。
public int hashCode() {
int h = hash;
if (h == 0) {
int off = offset;
char val[] = value;
int len = count;
//关键算法在这里：选31作为乘数的原因，是为了优化效率。因为31等于2的5次方减1，方便做位移操作。
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}
首先，哈希函数的原理是通过单向数学函数把原始数据映射到一个有限区间。最简单的方法就是乘法和除法取模。这里Java团队用的是乘法。原理用大白话讲就是，放大效应。我们把100以内的一个较小的数字做乘法放大很多倍变成10000，映射到一个大空间之后，样本的密度当然就变得稀疏了。著名的MD5加密后的密码有128位，可见样本空间的的巨大。另外，哈希算法的另一个特性就是不可逆性。做乘法容易，反过来因式分解就难了。哈希值被用来做加密算法就是这个道理。这里我们不展开。
String的哈希算法基于char。对每一个字符本身哈希值乘上一个乘数，然后求和。这里这个乘数就是魔法数字。至于选31的原因，还是看看Bloch是怎么说的：
之所以选择31，是因为它是个奇素数，如果乘数是偶数，并且乘法溢出的话，信息就会丢失，因为与2相乘等价于移位运算。使用素数的好处并不是很明显，但是习惯上都使用素数来计算散列结果。31有个很好的特性，就是用移位和减法来代替乘法，可以得到更好的性能：31*i==(i«5)-i。现在的VM可以自动完成这种优化。
所以，素数的功效只是个传说。关键是避免偶数。比如*16等于右位移4位，在前面加4个0。溢出之后数据丢失。
0000 1111
>>4 0000 0000 //*16相当于右位移四位>>4
哈希值的优化
首先，为什么要优化？
散列值是存放在32bit的int里。2进制32位带符号的表值范围从-2147483648到2147483648。前后大概40亿。
(0)111 1111 1111 1111 1111 1111 1111 1111 //最大int:2147483648
(1)000 0000 0000 0000 0000 0000 0000 0000 //最小int:-2147483648
如果散列均匀的话，基本很难重复。但问题在于，HashMap和HashSet的大小都收到机器内存的限制，一般为2^30，大概刚刚超过10亿。所以散列值出来以后，是要对数组长度取模的。根据前文的阐释，如果数组的长度是2的整数幂的话，取模相当于做低位掩码。
可以做个试验（实验的原文在此《An introduction to optimising a hashing strategy》），352个随机字符串各自都有唯一的散列值。但用低位掩码，只取了它们的低位之后，看看会不会有碰撞？
如上图所示，当HashMap数组的大小是512，使用哈希码的低九位作为掩码。可以看到，尽管原始的哈希码是唯一的，仍然有大约30%的关键字会冲突。
为了减少取模操作对散列效果造成的影响，HashMap使用了扰动函数。在Java 7里就是我们之前看到的一连串右位移加异或操作。
//初始哈希值做进一步优化（注：^为“异或”操作）
//异或：每一位上的值相同返回0，不同返回1。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
在Java 8里的实现变得更加得简单了：只是一次16右位移加异或操作。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
具体细节，请看下图，
从图中可以看到，右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来提高低位的随机性。这样当我们再用低位掩码，只取散列值低位做数组访问下标的时候，冲突就更少一些。具体效果请看看第三列，用低9位掩码的情况下，冲突降低了大概10%。
另外可以看到，相比Java 7的做四次异或混合，Java 8只做了一次。可能是发现做多了碰撞的改善也有限，折中一下，为了提升效率就只做一次异或扰动。
HashMap和HashSet的泛型
前文提到HashMap的put()方法在插入新元素之前，要检查新元素的key，是否和已有元素重复。检查的过程要做两次判断，并要求都为真：
- hashCode()值是否相同
- equals()是否为真
具体的判断代码如下：
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
这里的逻辑很清楚。而且和hashCode()本身的定义也是相符的：两个equals()判断为真的对象，其哈希值也应该相等。
Java的容器都支持泛型。如果HashMap中的自定义元素没有重写hashCode(),equals()这两个函数的时候，就会破坏HashMap元素的唯一性。因此在定义类的时候要注意重写这两个方法。
public class Matrix {
//constructor
public Matrix(int a,int b,int c,int d){
matrix=new int[2][2];
matrix[0][0]=a;
matrix[0][1]=b;
matrix[1][0]=c;
matrix[1][1]=d;
};
//fields
private int[][] matrix;
}
上面代码举了一个矩阵Matrix做元素的例子。Matrix其实就是一个二维数组。在重写之前，Array的hashCode(),equals()方法都继承自Object。array1.equals(array2)其实是判断等价array1 == array2。 hashCode()返回的是对象引用的地址。
所以值相等的两个矩阵对象m1和m2，都会被插入HashMap中。
HashSet<Matrix> hs = new HashSet<Matrix>();
Matrix m1 = new Matrix(1,2,3,4);
Matrix m2 = new Matrix(1,2,3,4);
hs.add(m1);
System.out.println(hs.contains(m1));
System.out.println(hs.contains(m2));
}
//OutPut:
//true
//false
这时候，要判断两个Array的值是否相等，可以用静态方法Arrays.equals(int[] a, int[] b), 和Arrays.hashCode(int[] a)。
public class Matrix {
@Override
public int hashCode(){
int[] hash=new int[2];
for(int i=0;i<2;i++){
hash[i]=Arrays.hashCode(matrix[i]);
}
return Arrays.hashCode(hash);
}
@Override
public boolean equals(Object o){
Matrix inM=(Matrix)o;
for(int i=0;i<2;i++){
if(!Arrays.equals(inM.matrix[i],this.matrix[i])){
return false;
}
}
return true;
}
//constructor
public Matrix(int a,int b,int c,int d){
matrix=new int[2][2];
matrix[0][0]=a;
matrix[0][1]=b;
matrix[1][0]=c;
matrix[1][1]=d;
};
//fields
private int[][] matrix;
}
再测试一下，现在就是根据值来判断是否已有相同的键值了。
HashSet<Matrix> hs = new HashSet<Matrix>();
Matrix m1 = new Matrix(1,2,3,4);
Matrix m2 = new Matrix(1,2,3,4);
Matrix m3 = new Matrix(5,6,7,8);
hs.add(m1);
System.out.println(hs.contains(m1));
System.out.println(hs.contains(m2));
System.out.println(hs.contains(m3));
}
//OutPut:
//true
//true
//false
另外HashSet因为后台也是用HashMap来控制元素唯一性的，也适用此方法。
！！注意：Map和Set里永远不要用mutable的数据类型
上面仅仅是个例子，但实际工作中，千万不要用Array这种mutable的数据类型为Map和Set赋值。
Mutable Objects: When you have a reference to an instance of an object, the contents of that instance can be altered Immutable Objects: When you have a reference to an instance of an object, the contents of that instance cannot be altered
Java虽然没有指针，但基本到处都是引用。所谓mutable就是指当我获得这个对象的引用时，可以改变它的值。Array就是典型的mutable。
int[]a={1,2,3};
a[0]=10; //改变的直接是a[0]的值
System.out.println(a[0]+" "+a[1]+" "+a[2]);
//Output: 10 2 3
这种随便改的特性，用到HashMap这种需要保证元素key值唯一性的容器里，想想都很可怕。
Java里Immutable的典型就是String了。官方的解释如下：
Once you assign a string object, that object can not be changed in memory. In summary, what you did is to change the reference of “a” to a new string object. Java String is immutable, String will Store the value in the form of object.
如上图所示，如果给一个已赋值的String重新赋值，结果String的引用被重新指向了一个新创建的对象。所以当把一个String当参数传进函数的时候要小心了，外部的String对象并不是被改变。
常见哈希算法观赏
下面是观赏时间，请大家赏玩，祝大家周末愉快：）
class GeneralHashFunctionLibrary
{/*RSHash*/
public long RSHash(String str)
{
int b = 378551;
int a = 63689;
long hash = 0;
for(int i = 0; i < str.length(); i++)
{
hash = hash * a + str.charAt(i);
a = a * b;
}
return hash;
}
/*JSHash*/
public long JSHash(String str)
{
long hash = 1315423911;
for(int i = 0; i < str.length(); i++)
hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));
return hash;
}
/*PJWHash*/
public long PJWHash(String str)
{
long BitsInUnsignedInt = (long)(4 * 8);
long ThreeQuarters = (long)((BitsInUnsignedInt * 3) / 4);
long OneEighth = (long)(BitsInUnsignedInt / 8);
long HighBits = (long)(0xFFFFFFFF)<<(BitsInUnsignedInt-OneEighth);
long hash = 0;
long test = 0;
for(int i = 0; i < str.length(); i++)
{
hash = (hash << OneEighth) + str.charAt(i);
if((test = hash & HighBits) != 0)
hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
return hash;
}
/*ELFHash*/
public long ELFHash(String str)
{
long hash = 0;
long x = 0;
for(int i = 0; i < str.length(); i++)
{
hash = (hash << 4) + str.charAt(i);
if(( x = hash & 0xF0000000L) != 0)
hash ^= ( x >> 24);
hash &= ~x;
}
return hash;
}
/*BKDRHash*/
public long BKDRHash(String str)
{
long seed = 131;//31131131313131131313etc..
long hash = 0;
for(int i = 0; i < str.length(); i++)
hash = (hash * seed) + str.charAt(i);
return hash;
}
/*SDBMHash*/
public long SDBMHash(String str)
{
long hash = 0;
for(int i = 0; i < str.length(); i++)
hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
return hash;
}
/*DJBHash*/
public long DJBHash(String str)
{
long hash = 5381;
for(int i = 0; i < str.length(); i++)
hash = ((hash << 5) + hash) + str.charAt(i);
return hash;
}
/*DEKHash*/
public long DEKHash(String str)
{
long hash = str.length();
for(int i = 0; i < str.length(); i++)
hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);
return hash;
}
/*BPHash*/
public long BPHash(String str)
{
long hash=0;
for(int i = 0;i < str.length(); i++)
hash = hash << 7 ^ str.charAt(i);
return hash;
}
/*FNVHash*/
public long FNVHash(String str)
{
long fnv_prime = 0x811C9DC5;
long hash = 0;
for(int i = 0; i < str.length(); i++)
{
hash *= fnv_prime;
hash ^= str.charAt(i);
}
return hash;
}
/*APHash*/
long APHash(String str)
{
long hash = 0xAAAAAAAA;
for(int i = 0; i < str.length(); i++)
{
if((i & 1) == 0)
hash ^=((hash << 7) ^ str.charAt(i) ^ (hash >> 3));
else
hash ^= (~((hash << 11) ^ str.charAt(i) ^ (hash >> 5)));
}
return hash;
}
}